/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <fstream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc;
	
	// Open index page file
	if((rc = pf.open(indexname, mode)) < 0)
		return rc;
	
	char buf[PageFile::PAGE_SIZE];
	memset(buf, 0, PageFile::PAGE_SIZE);
		
	// If there's no read error, index already exists, so load metadata
	if((rc = pf.read(METADATA, buf)) == 0)
	{
		memcpy(&rootPid, buf, sizeof(PageId));
		memcpy(&treeHeight, buf + TREEHEIGHT_OFFSET, sizeof(int));
	}

    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	RC rc;
	
	char buf[PageFile::PAGE_SIZE];
	memset(buf, 0, PageFile::PAGE_SIZE);
	
	// Write metadata to disk
	memcpy(buf, &rootPid, sizeof(PageId));
	memcpy(buf + TREEHEIGHT_OFFSET, &treeHeight, sizeof(int));
	
	// Even if you can't write to disk, you still have to close the index file, so don't bother with errors
	pf.write(METADATA, buf);

	// Close index page file
	if((rc = pf.close()) < 0) 
		return rc;
	
    return 0;
}

/*
 * Find the parent page id of the node containing the search key
 * @param searchkey[IN] the key to look for
 * @param currentPid[IN] the pid of the node that the key is in
 * @param parentPid[OUT] the page id of the parent of the node that the key is in
 * @return error code. 0 if no error
 */
RC BTreeIndex::parent(int searchKey, PageId currentPid, PageId& parentPid)
{
	BTNonLeafNode nonleaf;
	PageId curPid;
	RC rc;
	int currentHeight = 1;
	
	// Always start at root node
	curPid = rootPid;

	if(curPid == currentPid)
	{
		parentPid = curPid;
		return 0;
	}
	
	// While you haven't found the right pid
	while(currentHeight != treeHeight && curPid != currentPid)
	{
		// Read current page into a nonleaf node
		if((rc = nonleaf.read(curPid, pf)) < 0)
			return rc;
		
		parentPid = curPid;
		
		// Try to locate child pointer
		if((rc = nonleaf.locateChildPtr(searchKey, curPid)) < 0)
			return rc;

		currentHeight++;
	}
	
	return 0;
}
/*
 * Insert (key, rid) pair into a leaf node
 * @param leafnode[IN] the leafnode that the key, rid pair is being inserted into
 * @param pid[IN] the pid of the leaf node
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insertInLeaf(BTLeafNode& leaf, PageId pid, int key, const RecordId& rid)
{
	RC rc;
	
	// Insert into leaf
	if((rc = leaf.insert(key, rid)) < 0)
		return rc;
		
	// Write leaf page to disk
	if((rc = leaf.write(pid, pf)) < 0)
		return rc;

	return 0;
}
 
/*
 * Insert nodes into parent, splitting parent if necessary
 * @param leftpid[in] the pid of the left node
 * @param key[IN] the midkey to be moved up into the parent
 * @param rightpid[IN] the pid of the right node
 * @return error code. 0 if no error
 */
RC BTreeIndex::insertInParent(PageId leftPid, int midKey, PageId rightPid)
{
	PageId parentPid;
	BTNonLeafNode parentNode;
	RC rc;
	
	// If left node is the root, create a new root
	if(leftPid == rootPid)
	{		
		BTNonLeafNode root;
		
		if((rc = root.initializeRoot(leftPid, midKey, rightPid)) < 0)
			return rc;
		
		// Get new pid for root
		rootPid = pf.endPid();
		
		if((rc = root.write(rootPid, pf)) < 0)
			return rc;
		
		treeHeight++;
	}
	
	// Otherwise, find and read the parent node of the left node
	else if((rc = parent(midKey, leftPid, parentPid)) == 0)
	{
		
		if((rc = parentNode.read(parentPid, pf)) < 0)
			return rc;
		
		// If parent still has room, insert into parent
		if(parentNode.getKeyCount() != BTNonLeafNode::MAX_NONLEAF_NUM_KEY)
		{
			// insert key into parent node and write to disk
			if((rc = parentNode.insert(midKey, rightPid)) < 0)
				return rc;
				
			if((rc = parentNode.write(parentPid, pf)) < 0)
				return rc;
		}
		
		// Otherwise, have to split parent
		else
		{
			BTNonLeafNode sibling;
			int parentMidKey;
			PageId siblingPid;
			
			// Get new pid for sibling
			siblingPid = pf.endPid();
			
			// Insert and split parent node
			if((rc = parentNode.insertAndSplit(midKey, rightPid, sibling, parentMidKey)) < 0)
				return rc;
			
			// Write nodes to disk
			if((rc = parentNode.write(parentPid, pf)) < 0)
				return rc;
				
			if((rc = sibling.write(siblingPid, pf)) < 0)
				return rc;
			
			// Recursively insert nodes into parents
			if((rc = insertInParent(parentPid, parentMidKey, siblingPid)) < 0)
				return rc;
		}
	}
	
	// Error if could not find parent
	else
		return rc;
	
	return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	PageId pid;
	IndexCursor cursor;
	BTLeafNode leaf;
	
	// If no nodes in index, create a node and start populating index
	if(rootPid == -1)
	{
		// Let rootPid be the first index page after the metadata page
		rootPid = 1;
		
		// Let tree height be 1
		treeHeight = 1;
		
		// Read insert key into root and write to disk
		if((rc = leaf.insert(key, rid)) < 0)
			return rc;
		
		if((rc = leaf.write(rootPid, pf)) < 0)
			return rc;
	}
	
	// Otherwise find position to insert
	else
	{
		// Find page id of correct leaf using locate
		BTLeafNode leaf;
		
		// Try to locate insertion position; this call will return an error value, but 
		// will also return the page id where the key should be inserted if no other errors
		if((rc = locate(key, cursor)) != RC_NO_SUCH_RECORD && rc != 0)
			return rc;

		// Read page into leaf
		if((rc = leaf.read(cursor.pid, pf)) < 0)
			return rc;
		
		// If leaf is already full, have to split and create a new node
		if(leaf.getKeyCount() == BTLeafNode::MAX_NUM_KEY)
		{
			
			BTLeafNode sibling;
			int midKey;
			
			// Get next available page id for sibling
			PageId siblingPid = pf.endPid();

			// Split leaf into two separates leaves
			if((rc = leaf.insertAndSplit(key, rid, sibling, midKey)) < 0)
				return rc;
						
			// Set next node pointer for right node
			if((rc = sibling.setNextNodePtr(leaf.getNextNodePtr())) < 0)
				return rc;
			
			// Set next node pointer for left node
			if((rc = leaf.setNextNodePtr(siblingPid)) < 0)
				return rc;
			
			// Insert into leaf node and write to disk
			if((rc = leaf.write(cursor.pid, pf)) < 0)
				return rc;
			
			if((rc = sibling.write(siblingPid, pf)) < 0)
				return rc;
			
			// Insert leaves into parent
			if((rc = insertInParent(cursor.pid, midKey, siblingPid)) < 0)
				return rc;
		}
			
		// Else, insert key into leaf normally
		else
		{
			if((rc = insertInLeaf(leaf, cursor.pid, key, rid)) < 0)
				return rc;
		}
	}
	
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	BTLeafNode leaf;
	BTNonLeafNode nonleaf;
	PageId curPid;
	RC rc;
	int currentHeight = 1;
	
	// Always start at root node
	curPid = rootPid;
	
	// While you're not at the leaf level
	while(currentHeight != treeHeight)
	{
		// Read current page into a nonleaf node
		if((rc = nonleaf.read(curPid, pf)) < 0)
			return rc;
		
		// Try to locate child pointer
		if((rc = nonleaf.locateChildPtr(searchKey, curPid)) < 0)
			return rc;

		currentHeight++;
	}

	// When you're at the leaf level, read current page into a leaf node
	if((rc = leaf.read(curPid, pf)) < 0)
		return rc;

	// Set cursor page id to current page id
	cursor.pid = curPid;
	
	// Try to locate search key in node
	if((rc = leaf.locate(searchKey, cursor.eid)) < 0)
		return RC_NO_SUCH_RECORD;

    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode leaf;
	RC rc;
	
	// If cursor is pointing to metadata page, flag an error
	if(cursor.pid == METADATA)
		return RC_INVALID_CURSOR;
	
	// Otherwise, if cursor is pointing to a negative pid, leaf has no siblings
	else if(cursor.pid == -1)
		return RC_INVALID_PID;
	
	// Read leaf node
	if((rc = leaf.read(cursor.pid, pf)) < 0)
		return rc;
	
	// Read entry from leaf node
	if((rc = leaf.readEntry(cursor.eid, key, rid)) < 0)
		return rc;
	
	// If entry was the last one, move cursor to first entry in next node
	if(cursor.eid == leaf.getKeyCount() - 1)
	{
		cursor.pid = leaf.getNextNodePtr();
		cursor.eid = 0;
	}
	
	// Otherwise, move cursor to next entry in current node
	else
		cursor.eid++;
	
    return 0;
}
